A correlator is a device that is capable of detecting the presence of a replica with, for example, added noise, of a finite length reference sequence of data bits from within a relatively long signal sequence of bits. Correlators have many applications, however, one of the most widely recognized uses is in spread spectrum communications where a received signal is digitized and correlated with a known reference sequence in order to, for example, temporally align the received signal with other signals.
An N-bit digital correlator operates to compare an incoming data stream with N bits of a reference data word. The correlator provides a measure of the amount of correlation existing between corresponding bits in the signal data stream and the reference word, usually when the data stream is received in a noisy environment. One such measure is the number of bit agreements, however, other measures can also be used. Whenever N signal bits correspond exactly to the N-bit reference word, it is said that “perfect” correlation has occurred. Under such circumstances, the correlator output is maximized. A simplified version of the mathematical formula that represents a correlation calculation is illustrated in equation 1 below, wherein the correlation, CA,B, of sequence Ai, with the sequence Bi, where i ε (1 . . . n) is mathematically denoted by:                               C                      A            ,            B                          =                              ∑                          i              =              1                        n                    ⁢                                    A              i                        ·                          B              i                                                          (        1        )            
In communication applications, it is often desirable to calculate the correlation function between a sliding sub-sequence and a fixed sequence. For example, a sub-sequence of length n, from a larger sequence A of length m, can be correlated to a second sequence B of length n. The correlation is done successively on all of the sub-sequences of A such that the correlation calculated will be a function of the offset t from the beginning of sequence A to the location where the matching, or most highly correlated, sub-sequence of A begins. Equation 2, shown below, denotes the mathematical formula for calculating the correlation, CA,B(t), between the sliding sub-sequence of a longer sequence Ai and a finite sequence Bi.                                           C                          A              ,              B                                ⁡                      (            t            )                          =                              ∑                          i              =              1                        n                    ⁢                                    A                              t                +                i                                      *                          B              i                                                          (        2        )            where t ε (1 . . . m), and i ε (1 . . . n)
The correlation calculated using equation 2 is especially useful when a known sequence is to be detected within an infinite input sequence, for example, in a noisy environment as exemplified in the chart shown in FIG. 6. As can be seen in the chart in FIG. 6, correlation C(t) reaches a maximum value when t=12. This makes sense since as shorter finite sequence B is sequentially “slid” across longer sequence A in increments of t, while performing a comparison between each corresponding value of A and B, it can be seen that sequence B and sequence A match identically at t=12.
In many digital applications, such as in communications, the shorter, or finite, sequence is binary, and assumes the value of either −1 or +1. Accordingly, if one considers equation 2, with the assumption that B can assume only the value −1 or +1, no multiplication calculations are needed. The total number of calculations needed to calculate the correlation in this case is m*(n−1). The calculations required are either addition or subtraction calculations, as determined by the values of the B bits. This same principle also applies when A, or the longer sequence, is a binary sequence having values of −1 or +1.
One known circuit by which a correlation is calculated for a short binary sequence is shown in FIG. 1. Sequence A is serially input to the shift register, (10), one symbol at a time. The shift register (10) comprises n shift register blocks each block comprising a number of flip-flops corresponding to the number of bits required to represent each symbol in A. The shift register, therefore, stores the last n values of A, which comprise the subsequence to be correlated.
Sequence B is initially fed into and stored in feedback shift register (11) which is comprised of single-bit blocks. For each new symbol of A introduced into shift register (10), shift register (11) completes a full rotation, applying all n values of B to the MUX (16) selector input. The accumulator register (17) accumulates the output of MUX (16) and is reset each time a new subsequence is entered into shift register (10), i.e., each time a new symbol of sequence A is entered. Thus, the reset for accumulator register (17) and the clock for shift register (10) occur at a frequency f and the clock pulses for accumulator register (17), divide-by-n counter (13) and shift register (11) occur at frequency n×f.
The correlation for every sub-sequence of A is calculated as follows: The Divide-by-n counter (13) and the n-bit MUX (12) scan the sub-sequence A, stored in shift register (10), and assert all n values of the current sub-sequence to the inputs of the Adder (15) and the Subtractor (14). Shift Register (11), concurrently with the scanning of the sub-sequence values of A, rotates and scans the n values of the B sequence and presents all of the values of the B sequence to the selector input of MUX (16). MUX (16), which selects either the output of Adder (15) or Subtractor (16), is governed by the value of the B sequence bits. A value of +1 selects addition (Adder (15)), and −1 selects subtraction (Subtractor (16)). As a result of the application of positive or negative signals at the selector input of MUX (16), Accumulator-Register (17) determines the correlation value by adding or subtracting A sequence values to or from, respectively, the present value in Accumulator-Register (17). Thus, the accumulated value stored in Accumulator-Register (17) is equivalent to the accumulated value of the product At+i*Bi.
There are variations of the prior art method just described, and the circuit shown in FIG. 1 is just an example. However, all prior art implementations require n*(m−1) addition or subtraction calculations to determine the correlation value.
A similar situation to the short binary sequence situation described above arises when the finite sequence being correlated is a long binary sequence. This situation is different, in some respects, from the short sequence case discussed above and similar in other respects. FIG. 2 illustrates a typical binary long sequence approach according to the prior art. The long sequence situation arises when a large amount of data is being input to the system over a significant amount of time. As can be seen in FIG. 2, in the long sequence case, sequence A is input to shift register (20) and each of the n bits of A is sequentially selected using MUX 22 and Divide-by-n counter (23). Similar to the short sequence case discussed above in reference to FIG. 1, sequence B is initially fed into and stored in feedback shift register (21) which is comprised of single-bit blocks. As each bit of sequence A is output from MUX (22), the outputted bit is used to select, using MUX (26), either the output of Adder (25) or the output of Subtractor (24), respectively. As a result, each respective bit of sequence B is accumulated in Accumulator Register (27), thereby determining the correlation value of A and B.
A problem arises in the prior art, however, in that all prior art approaches require a large number of computations to achieve the correlation. Each calculation requires a finite amount of time and expends a finite amount of energy. Therefore, as the number of computations increases, so does the time and energy required to calculate the correlation. Both of these resources, time and energy, are extremely valuable to the hardware and system designer and any measures that can be taken to reduce unnecessary expenditure of these resources is typically welcome. As a general rule, fast calculation of the correlation can be achieved by expending more energy per unit time or, alternatively, energy can be preserved by solving fewer computations per unit time. However, it is impossible to achieve both high speed and low energy expenditure using the prior art methods described above. A solution to this dilemma requires a reduction in the number of computations required to achieve the correlation value.